package org.example.likou150.circularList;

// https://leetcode.cn/problems/partition-list/?envType=study-plan-v2&envId=top-interview-150
public class Partition {

    public ListNode partition(ListNode head, int x) {
        ListNode returnNode = new ListNode(0);
        ListNode leftNode = returnNode;
        ListNode rightHeadNode = new ListNode(0);
        ListNode rightNode = rightHeadNode;
        while (head!=null){
            if(head.val < x){
                leftNode.next = head;
                leftNode = leftNode.next;
            }else {
                rightNode.next = head;
                rightNode = rightNode.next;
            }
            head = head.next;
        }
        rightNode.next = null;
        leftNode.next = rightHeadNode.next;
        return returnNode.next;
    }

 public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
}
